package com.fengdi.book.hard.design;

import java.util.PriorityQueue;

class MedianFinder {
    private PriorityQueue<Integer> max; // 大根堆，左侧，升序
    private PriorityQueue<Integer> min; //小根堆，右侧，降序

    public MedianFinder() {
        this.max = new PriorityQueue<>((a,b) -> b - a);
        this.min = new PriorityQueue<>();
    }

    public void addNum(int num) {
        this.min.add(num);
        if(!this.max.isEmpty() && !this.min.isEmpty() && this.min.peek() < this.max.peek()) {
            this.max.add(this.min.poll());
        }

        if(this.max.size() > this.min.size() + 1) {
            this.min.add(this.max.poll());
        }

        if(this.min.size() > this.max.size() + 1) {
            this.max.add(this.min.poll());
        }
    }

    public double findMedian() {
        if(this.max.size() > this.min.size()) return this.max.peek();
        if(this.min.size() > this.max.size()) return this.min.peek();
        return ((double) this.min.peek() + (double) this.max.peek()) / 2.0D;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
